Matfyz Wiki

Zkouška - 22.01.2013

Davpe at 2013-01-24 16:46:45

Kviz:
(Nepřišel mi úplně jednoduchý, měl jsem 11/15 a na postup je potřeba 11 bodů. Dva lidi z něj vyletěli, plný počet bodů neměl nikdo.)

Na co si vzpomínám

  1. Reflexní agent
    [x] záleží na posledním vjemu
    [] záleží na posloupnosti vjemů od narození

  2. Racionální agent
    [x] Maximalizuje očekávanou míru vstupu
    [] Maximalizuje skutečnou míru vstupu

  3. Co je standardizace stranou
    [x] Přejmenování proměnných

  4. Co je magická množina?
    [x] něco s dopředným řetězením

  5. Který algoritmus vrací více řešení
    [x] Genetické algoritmy
    [] Horolezecká metoda
    [] Simulované žíhání
    [] A*

  6. Na Marsu jsou dva vozítka, která mezi sebou nekomunikují, jaké NENÍ prostředí?
    [] stochastické
    [] dynamické
    [] multiagentní
    [] spojité

(správná odpověď NENÍ stochastické)

  1. Který algoritmus NENÍ úplný
    [x] DFS
    [] BFS

  2. Vztah mezi stavem a uzlem
    [] žádný
    [] jsou stejné
    [x] stav může být ve více uzlech
    [] uzel může obsahovat více stavů

  3. Co je lokální optimum.
    [] Všude kolem je horší hodnota
    [x] Neexistuje bod z okolí, který by nabýval lepší hodnoty.

(tady pozor, nemyslí se RYZE lokální optimum, ale lokální optimum takže to může vypadat i takhle ____/ )

  1. Co je hrozba v plánu
    [x] Porušení kauzální vazby
    [] Otevřený cíl

  2. Čím se nezabývá znalostní inženýrsví
    [x] Programováním něčeho (myslím že unifikace)
    [] Získávání znalostí od expertů

  3. Co platí pro dvojici (A, B) která je hranově konzistentní
    (správná odpověď není, pro všechny dvojice platí něco - v definici to asi platí jen jedním směrem)

Ustní zkouška (moje zadání)
Gran na vrcholech A, B, C hrany AB, BC. Převeďtě obarvení grafu barvami 1 a 2 na splnitelnost formule a napiště ji. Formule by snadno měla jít rozšířit pro libovolná počet barev a libovolný graf. Demonstrujte DPLL a WalkSAT.
(graf byl v zadání definován jako orientovaný ale vzhledem k obarvování vrcholů to je jedno).

formule:

// Každý vrchol obarvi právě jednou barvou
(c(A, 1) OR c(A, 2)) AND NOT(c(A, 1) AND c(A, 2)) AND
(c(B, 1) OR c(B, 2)) AND NOT(c(B, 1) AND c(B, 2)) AND
(c(C, 1) OR c(C, 2)) AND NOT(c(C, 1) AND c(C, 2)) AND
// Sousední vrcholy nesmí mít stejné barvy
NOT (c(A, 1) AND c(B,1)) AND
NOT (c(A, 2) AND c(B,2)) AND
NOT (c(B, 1) AND c(C,1)) AND
NOT (c(B, 2) AND c(C,2))

pak jsem ji převedl do CNF (což bylo easy protože NOT (a AND b) stačilo nahradit (NOT a OR NOT b) a velice stručně popsal oba algoritmy.

U ústní neměl k formuli připomínky, ptal se mě jak funguje WalkSAT, řekl jsem, že je to náhodná procházka, pak jsme chvíli debatovali jak funguje DPLL a kterou heuristiku (ryzí klauzule/jednotková proměnná) použít jako první a proč (heuristika ryzí proměnné může po aplikaci vygenerovat jak jiné ryzí proměnné tak nové jednotkové klauzule, proto je lepší použít ji první).

Pak vzal do ruky kvíz, řekl mi, že mi moc nešlo lokální prohledávání (dvě otázky co byly špatně byly právě na něj), tak jsem si obě otázky opravil (se značnými nápovědami Bartáka - měl jsem takový bordel v jeho terminologii, že jsem nemohl uhodnout jak říká takovému stavu který vypadá jako křivka x^3 .... po mém hádání typu plošina, hřeben, rovina, převis kreslil obrázek tak dlouho než nakreslil obrázek celého člověka a mě konečně došlo že se tomu říká rameno :D)

Známka 1. Barták neuvěřitelně radil, když jsem něco řekl špatně, tak mi nakrslil protipříklad, dokud jsem se neopravil, opravdu pohodička.

(celkově měla spousta lidí jedničku občas dvojka)

Ostatní zadání
Plánování (jeřáb a palety na sobě)
CSP
Porovnání A*, IDA*, MA* atd. a něco o heuristikách.
Databáze znalostí, sylogismy, věty na způsob Sokratés je člověk. Lidé jsou smrtelní. Sokratés je smrtelný.